#include<stdio.h>
#include<stdlib.h>

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
void print_Arr(int arr[],int n){
    for(int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    putchar('\n');
}
void insert_sort(int arr[],int n){
    for(int i=1;i<n;i++){
        int key=arr[i];//填坑法，留出待插入位置作为坑保存下来
        int j=i-1;//从i的左边比较起，因为i地左边时排好序的，和左边比较相当于和i左边的所有数中最大值比较
        while(j>=0 && arr[j]>key){
            arr[j+1]=arr[j];//每次向前移动一个位置（前面的元素往后面一个位置逐位保存，最后找到arr[j]<key的位置时候a[j+1]已经被a[j+1+1]保存下来了，可以和key交换），丢失的只有之前保存的key 即arr[i]
            j--;
        }
        //找到arr[j]<key的位置后插入key
        arr[j+1]=key;
        print_Arr(arr,n);
    }
}
int main(int argc,char const* argv[]){
    int arr[6]={30,40,10,14,15,20};
    insert_sort(arr,6);
    return 0;
}